package com.leetcodehot.problems;

import java.util.Arrays;

public class problems97 {
    /**
     * 记忆化搜索
     */
    /*
    private char[] c1;
    private char[] c2;
    private char[] c3;

    public boolean isInterleave(String s1, String s2, String s3) {
        c1 = s1.toCharArray();
        c2 = s2.toCharArray();
        c3 = s3.toCharArray();
        int n1 = c1.length;
        int n2 = c2.length;
        int n3 = c3.length;
        if (n1 + n2 != n3) return false;
        int[][] memo = new int[n1 + 1][n2 + 1];
        // 初始化 -1 true 1 false 0
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(n1 - 1, n2 - 1, n3 - 1, memo);
    }

    private boolean dfs(int i, int j, int k, int[][] memo) {
        if (i < 0) {
            boolean flag = true;
            for (int t1 = j, t2 = k; t1 >= 0; t1--, t2--) {
                if (c2[t1] != c3[t2]) {
                    flag = false;
                    break;
                }
            }
            return flag;
        }
        if (j < 0) {
            boolean flag = true;
            for (int t1 = i, t2 = k; t1 >= 0; t1--, t2--) {
                if (c1[t1] != c3[t2]) {
                    flag = false;
                    break;
                }
            }
            return flag;
        }
        if (memo[i][j] != -1) {
            return memo[i][j] == 1;
        }
        if (c1[i] == c3[k] || c2[j] == c3[k]) {
            boolean ans = false;
            if(c1[i] == c3[k]) {
                ans = ans || dfs(i - 1, j, k - 1, memo);
            }
            if(c2[j] == c3[k]) {
                ans = ans || dfs(i, j - 1, k - 1, memo);
            }
            memo[i][j] = ans ? 1 : 0;
            return ans;
        } else {
            memo[i][j] = 0;
            return false;
        }
    }
    */

    /**
     * 递推
     */
    /*
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        if (n + m != s3.length()) {
            return false;
        }
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();

        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int j = 0; j < m; j++) {
            f[0][j + 1] = c2[j] == c3[j] && f[0][j];
        }
        for (int i = 0; i < n; i++) {
            f[i + 1][0] = c1[i] == c3[i] && f[i][0];
            for (int j = 0; j < m; j++) {
                f[i + 1][j + 1] = c1[i] == c3[i + j + 1] && f[i][j + 1] ||
                        c2[j] == c3[i + j + 1] && f[i + 1][j];
            }
        }

        return f[n][m];
    }
     */

    /**
     * 继续优化
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        if (n + m != s3.length()) {
            return false;
        }
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();

        boolean[] f = new boolean[m + 1];
        f[0] = true;
        for (int j = 0; j < m; j++) {
            f[j + 1] = c2[j] == c3[j] && f[j];
        }
        for (int i = 0; i < n; i++) {
            f[0] = c1[i] == c3[i] && f[0];
            for (int j = 0; j < m; j++) {
                f[j + 1] = c1[i] == c3[i + j + 1] && f[j + 1] ||
                        c2[j] == c3[i + j + 1] && f[j];
            }
        }
        return f[m];
    }
}
